package main.Q201_300;

import java.util.*;

public class Q221_230 {
    public static void main(String[] args) {
        System.out.println("Question221：最大正方形");
        System.out.println("Question222：完全二叉树的节点个数");
        System.out.println("Question223：矩形面积");
        System.out.println("Question224：基本计算器");
        System.out.println("Question225：用队列实现栈");
        System.out.println("Question226：翻转二叉树");
        System.out.println("Question227：基本计算器Ⅱ");
        System.out.println("Question228：汇总区间");
        System.out.println("Question229：多数元素Ⅱ");
        System.out.println("Question230：二叉搜索数中第K小的元素");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
}

class Question221{
    public int process(char[][] matrix,int r,int c,int len){
        int min=0,up=0,left=0;
        for (int i=r-1;i>=r-len;i--){//向上排查是否存在0
            if (matrix[i][c]=='0') break;
            up++;
        }
        for (int i=c-1;i>=c-len;i--){//向左排查是否存在0
            if (matrix[r][i]=='0') break;
            left++;
        }
        min=Math.min(up,left);
        return min;
    }
    public int maximalSquare(char[][] matrix) {
        int max=0,row=matrix.length,col=matrix[0].length;
        int[][] dp=new int[row][col];
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++){
                if (matrix[i][j]=='1'){
                    if (i-1>=0&&j-1>=0&&dp[i-1][j-1]!=0){
                        int len=(int)Math.sqrt(dp[i-1][j-1]);
                        int minLen=process(matrix,i,j,len);//能够扩展的最大长度
                        dp[i][j]=(1+minLen)*(1+minLen);
                    }else dp[i][j]=1;//左上不是正方形，自身组成正方形
                }
                max=Math.max(max,dp[i][j]);
            }
        }
        return max;
    }
}

class Question222{
    public int countNodes(TreeNode root) {
        int count=0;
        if (root==null) return count;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode curNode=queue.poll();
            count++;
            if (curNode.left!=null) queue.add(curNode.left);
            if (curNode.right!=null) queue.add(curNode.right);
        }
        return count;
    }
}

class Question223{
    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int areaTotal=0,areaA=0,areaB=0,areaGap=0;
        areaA=(ax2-ax1)*(ay2-ay1);//单独A面积
        areaB=(bx2-bx1)*(by2-by1);//单独B面积
        if (!(ax1>=bx2||bx1>=ax2)&&!(ay1>=by2||by1>=ay2)){//横纵均有重叠才有重叠面积
            int row=((ax2-ax1)+(bx2-bx1)-(Math.abs(bx2-ax2))-(Math.abs(bx1-ax1)))/2;//两倍重合部分
            int col=((ay2-ay1)+(by2-by1)-(Math.abs(by2-ay2))-(Math.abs(by1-ay1)))/2;
            areaGap=row*col;
        }
        areaTotal=areaA+areaB-areaGap;
        return areaTotal;
    }
}

class Question224{
    public int calculate(String s) {
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(1);
        int sign = 1;
        int result = 0;
        int n = s.length();
        int i = 0;
        while (i < n) {
            if (s.charAt(i) == ' ') {
                i++;
            } else if (s.charAt(i) == '+') {
                sign = stack.peek();
                i++;
            } else if (s.charAt(i) == '-') {
                sign = -stack.peek();
                i++;
            } else if (s.charAt(i) == '(') {
                stack.push(sign);
                i++;
            } else if (s.charAt(i) == ')') {
                stack.pop();
                i++;
            } else {
                long num = 0;
                while (i < n && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                result += sign * num;
            }
        }
        return result;
    }
}

class Question225{
    Deque<Integer> stack;
    public Question225() {
        stack=new LinkedList<>();
    }

    public void push(int x) {
        stack.addLast(x);
    }

    public int pop() {
        return stack.pollLast();
    }

    public int top() {
        return stack.peekLast();
    }

    public boolean empty() {
        return stack.isEmpty();
    }
}

class Question226{
    public TreeNode invertTree(TreeNode root) {
        reverse(root);
        return root;
    }
    public void reverse(TreeNode node){
        if (node==null) return;
        reverse(node.left);
        reverse(node.right);
        TreeNode temp=node.left;
        node.left=node.right;
        node.right=temp;
    }
}

class Question227{
    public int calculate(String s) {//
        int result=0;
        char[] str=s.toCharArray();
        StringBuffer processS=new StringBuffer();
        for (char c:str)//去除空格
            if (c!=' ') processS.append(c);
        str=processS.toString().toCharArray();
        Stack<String> stack=new Stack<>();
        StringBuffer num=new StringBuffer();
        char preOpt='+';
        for (int i=0;i<str.length;i++){
            if (str[i]>='0'&&str[i]<='9') num.append(str[i]);//数字累加
            else{
                switch (preOpt){
                    case '+':
                        stack.add(num.toString());
                        break;
                    case '-':
                        stack.add("-"+num.toString());
                        break;
                    case '*':
                        stack.add(String.valueOf(Integer.valueOf(stack.pop())*Integer.valueOf(num.toString())));
                        break;
                    case '/':
                        stack.add(String.valueOf(Integer.valueOf(stack.pop())/Integer.valueOf(num.toString())));
                        break;
                }
                preOpt=str[i];
                num.delete(0,num.length());
            }
        }
        switch (preOpt){//最后一个数
            case '+':
                stack.add(num.toString());
                break;
            case '-':
                stack.add("-"+num.toString());
                break;
            case '*':
                stack.add(String.valueOf(Integer.valueOf(stack.pop())*Integer.valueOf(num.toString())));
                break;
            case '/':
                stack.add(String.valueOf(Integer.valueOf(stack.pop())/Integer.valueOf(num.toString())));
                break;
        }
        while (!stack.isEmpty()){
            result+=Integer.valueOf(stack.pop());
        }
        return result;
    }
}

class Question228{
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<String>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < nums.length; ++i){
            if(!(i + 1 < nums.length && nums[i] == nums[i + 1] - 1)){
                if(sb.length() > 0) sb.append("->");
                sb.append(nums[i]);
                result.add(sb.toString());
                sb = new StringBuilder();
            } else{
                if(sb.length() == 0) sb.append(nums[i]);
            }
        }
        return result;
    }
}

class Question229{
    public List<Integer> majorityElement(int[] nums) {//摩尔投票法更高效
        List<Integer> list=new ArrayList<>();
        int count= nums.length/3;
        Map<Integer,Integer> map=new HashMap<>();
        for (int i=0;i< nums.length;i++){
            if (!map.containsKey(nums[i])){
                map.put(nums[i],1);
            }else map.put(nums[i],map.get(nums[i])+1);
        }
        for (Integer integer:map.keySet()){
            if (map.get(integer)>count) list.add(integer);
        }
        return list;
    }
}

class Question230{
    public int kthSmallest(TreeNode root, int k) {//非递归中序遍历
        int result=0,count=0;
        TreeNode curNode=root;
        Stack<TreeNode> stack=new Stack<>();
        while (!stack.isEmpty()||curNode!=null){
            if (curNode!=null){
                stack.push(curNode);//入栈
                curNode=curNode.left;//寻找左孩子
            }else {
                TreeNode temp=stack.pop();
                count++;
                if (count==k){
                    result= temp.val;
                    break;
                }
                curNode=temp.right;
            }
        }
        return result;
    }
}